package com.jlh.viewer.acm;

/**
 * Created by jlh
 * On 2017/4/12 0012.
 */
public class Solution {
    /**
     * 返回git树上两点的最近分割点
     *
     * @param matrix 接邻矩阵，表示git树，matrix[i][j] == '1' 当且仅当git树中第i个和第j个节点有连接，节点0为git树的跟节点
     * @param indexA 节点A的index
     * @param indexB 节点B的index
     * @return 整型
     */
    public int getSplitNode(String[] matrix, int indexA, int indexB) {
        boolean[] vis = new boolean[matrix.length];
        vis[0]=true;
        String[] resA= reslove(matrix,0,indexA,vis).split(",");
        String[] resB=reslove(matrix,0,indexB,vis).split(",");
        int i=0;
        for (;i<resA.length&&i<resB.length;i++){
            if (!resA[i].equals(resB[i]))
                return Integer.valueOf(resA[i-1]);
        }
        return Integer.valueOf(resA[i-1]);
    }
    public String reslove(String []matrix,int now,int index,boolean vis[]){
        if (now==index)
            return index+"";
        for (int i=0;i<matrix[now].length();i++){
            char flag = matrix[now].charAt(i);
            if (flag=='1'&&!vis[i]){
                vis[i]=true;
                String res = reslove(matrix,i,index,vis);
                if (!res.equals("")) {
                    vis[i]=false;
                    return now +"," +res;
                }
                vis[i]=false;
            }
        }
        return "";
    }
    public static void main(String[] args) {
        String []matrix= {"001","001","110"};
        int indexA=1,indexB=1;
        Solution solution = new Solution();
        System.out.println(solution.getSplitNode(matrix,indexA,indexB));
    }
}